#include "BTreeNode.h"
//test
using namespace std;

/*
 *        LEAF IMPLEMENTATION
 *
 */

/*
 * Initialize buffer to zero. So newly contruscted node is an empty node
 *
 */
BTLeafNode::BTLeafNode()
{
    memset(buffer, 0, PageFile::PAGE_SIZE);
}
/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */

RC BTLeafNode::read(PageId pid, const PageFile& pf)
{  
    return (pf.read(pid,buffer)); //error reading the pagefile 
}
    
/*
 * Set the buffer (data) of the node
 * @param buffer[IN] the data buffer to set
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::read(char * buf)
{
    memcpy(buffer, buf, PageFile::PAGE_SIZE);
}    
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */

RC BTLeafNode::write(PageId pid, PageFile& pf)
{ 
    return (pf.write(pid,buffer)); 
}
/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{ 
    //The first 4 bytes of each node contains the number of keys in that node
    int numKey=0;
    memcpy(&numKey, buffer, sizeof(int));
    return numKey;
    
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{   
   int numKey = getKeyCount();
    //check if node is full
    //maximum key: 1024-4(pid)-4(meta data) = 1016 bytes for 12 bytes of (RecordId, key) -> 84 entries
    if(numKey >= MAX_LEAF_ENTRY) {
        return RC_NODE_FULL;
    }
    
    int eid;
    //locate the spot to insert
    RC rc = locate(key, eid);
    
    //if no key>=searchkey, then we insert the pair to the end of the node
    //this is probably unecessary because eid will be equal to getKeyCount() 
    if(rc == RC_NO_SUCH_RECORD){
        eid = numKey;
    }
    
    //The first 4 bytes store meta data
    char* StartKey = buffer+sizeof(int);
    //make room for the new leaf entry
    //ex. (3)4, (3)12, (5)12, (6)12, 4
    int moveBufferSize = (numKey-eid)*LEAF_ENTRY_SIZE + sizeof(PageId);
    char* moveBuffer = (char*)malloc(moveBufferSize * sizeof(char));
    memcpy(moveBuffer, StartKey+eid*LEAF_ENTRY_SIZE, moveBufferSize);
    
    //insert the leaf entry
    memcpy(StartKey+eid*LEAF_ENTRY_SIZE,&key, sizeof(int));
    memcpy(StartKey+eid*LEAF_ENTRY_SIZE+sizeof(int), &rid, sizeof(RecordId));
    //put back the moveBuffer
    memcpy(StartKey+(eid+1)*LEAF_ENTRY_SIZE,moveBuffer, moveBufferSize);
    
    //increment the key count
    numKey++;
    memcpy(buffer, &numKey, sizeof(int));
    
    //free buffer memory
    free(moveBuffer);
    return 0; 


}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{      
    
    //Assuming that the sibling node is empty when the number of keys (the first 4 bytes) = 0
    
    int numKey = getKeyCount();
    //make sure the current node is full
    if(numKey < MAX_LEAF_ENTRY){
        return RC_INVALID_FILE_FORMAT;
    }

    //startEid is the first leaf entry to be split
    int startEid = numKey/2;
    PageId currentNodeNextPid = getNextNodePtr();
    //set siblingKey
    memcpy(&siblingKey, buffer+sizeof(int)+startEid*LEAF_ENTRY_SIZE+sizeof(RecordId), sizeof(int));
    
    //temporary variable to hold key and recID that will be copied to the sibling node
    int sibKey;
    RecordId sibRid;
    //split the entry with sibling node
    while(startEid<numKey){
        //insert entry to the sibling node
        if(readEntry(startEid,sibKey,sibRid)!=0){
            return RC_FILE_READ_FAILED;
        }
        if(sibling.insert(sibKey,sibRid)!=0){
            return RC_FILE_WRITE_FAILED;
        }
        
        //decrement key count for current node
        numKey--;
        memcpy(buffer, &numKey, sizeof(int));
        
        startEid++;
    }
    //restore the current Node Next PageId
    setNextNodePtr(currentNodeNextPid);
    
    // Set the sibling's next node pointer
    if(sibling.setNextNodePtr(currentNodeNextPid) !=0)
        return RC_INVALID_PID;
    
    //insert the new entry to sibling node
    if(key > siblingKey){
        if(sibling.insert(key,rid)!=0){
            return RC_FILE_WRITE_FAILED;
        }

         
    }else{
        if(insert(key,rid)!=0){
            return RC_FILE_WRITE_FAILED;
        }
    }
    
    //B+ tree will set this node's pointer to point to the sibling node
    return 0; 
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{
    //Note: the eid for first key is 0
    int numKey = getKeyCount();
    RecordId rid;
    int key;
    eid = 0;
    
    //traverse through the node
    while(eid<numKey){
        readEntry(eid,key,rid);
        if(key>=searchKey){
            return 0;
        }
        eid++;
    }
    
    //no keys are found
    return RC_NO_SUCH_RECORD;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{
    //This is only for leaf node!
    //take into accout that spacing of keys is different between leaf and nonleaf nodes
    if (eid < 0 || eid >= getKeyCount())
    {
        return RC_INVALID_CURSOR;
    }
    memcpy(&rid, buffer+sizeof(int)+eid*LEAF_ENTRY_SIZE,sizeof(RecordId));
    memcpy(&key, buffer+sizeof(int)+eid*LEAF_ENTRY_SIZE+sizeof(RecordId), sizeof(int));

    return 0; 
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{ 
    //This is for leaf node only!
    int numKey = getKeyCount();
    PageId pid;
    memcpy(&pid, buffer+sizeof(int)+numKey*LEAF_ENTRY_SIZE, sizeof(PageId));
    return 0; 

}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{ 
    if(pid<0)
        return RC_INVALID_PID;
    int numKey = getKeyCount();
    memcpy(buffer+sizeof(int)+numKey*LEAF_ENTRY_SIZE, &pid, sizeof(PageId));
    
    return 0; 


}
/*
 *        NON LEAF IMPLEMENTATION
 *
 */
/*
 * Initialize buffer to zero. So newly constructed node is an empty node
 *
 */
BTNonLeafNode::BTNonLeafNode() {
    memset(buffer, 0, PageFile::PAGE_SIZE);
}
/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{ 
    return (pf.read(pid,buffer));
}
    
/*
 * Set the buffer (data) of the node
 * @param buffer[IN] the data buffer to set
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::read(char * buf)
{
    memcpy(buffer, buf, PageFile::PAGE_SIZE);
}    
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{ 
    return (pf.write(pid,buffer));
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{
    int numKey=0;
    memcpy(&numKey, buffer, sizeof(int));
    return numKey;
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{ 
    int numKey = getKeyCount();
    //check if node is full
    //maximum key = 127 keys
    if(numKey >= MAX_NLEAF_ENTRY) {
        return RC_NODE_FULL;
    }
    //find the location to insert the new key and pid
    int entryNum=0;
    int current_key;

    int entrySize=0;
    while(entryNum<numKey){
        
        //page id comes before key
        memcpy(&current_key, buffer+sizeof(int)+entrySize+sizeof(PageId), sizeof(int));
        
        //if the new key is smaller than the current key, push back all the keys after this key
        //and insert the new (pid,key) entry
        //for example, if we have keyNum(3), pid(a), key(2), pid(b), key(3), pid(c), key(5), pid(d)
        //if we want to insert key(4), pid(f)
        //push back all the entry after entryNum=2: push back key(5),pid(d)
        //result: keyNum(4), pid(a), key(2), pid(b), key(3), pid(c),key(4), pid(f), key(5), pid(d)
        if(current_key>=key){
            int moveBufferSize = (numKey-entryNum) * NLEAF_ENTRY_SIZE;
            char* moveBuffer = (char*)malloc(moveBufferSize * sizeof(char));
            memcpy(moveBuffer, buffer+sizeof(int)+entrySize+sizeof(PageId), moveBufferSize);
            
            //add key first then pid
            memcpy(buffer+sizeof(int)+entrySize+sizeof(PageId), &key, sizeof(int));
            memcpy(buffer+sizeof(int)+entrySize+NLEAF_ENTRY_SIZE, &pid, sizeof(PageId));
            
            //add the buffer back in
            memcpy(buffer+sizeof(int)+entrySize+NLEAF_ENTRY_SIZE+sizeof(PageId), moveBuffer, moveBufferSize);
            
            //release memory
            free(moveBuffer);
            
            //increment key count
            numKey++;
            memcpy(buffer, &numKey, sizeof(int));
            return 0;
        }
        entryNum++;
        entrySize+=NLEAF_ENTRY_SIZE;
    }
    //if the program reaches this point, the new Key is greater than all the keys in the node
    //add the new entry to the end
    //Note: we add key first, the pid
    memcpy(buffer+(sizeof(int)+entrySize+sizeof(PageId)),&key, sizeof(int));
    memcpy(buffer+(sizeof(int)+entrySize+sizeof(PageId)+sizeof(int)), &pid, sizeof(PageId));
    
    
    //increment key count
    numKey++;
    memcpy(buffer,&numKey,sizeof(int));
    return 0; 
    //There would not be the case when the insert key for non-leaf node is smaller than all the existing 
    //keys in the node because the insert key is being pushed from leaf (or child non-leaf), which is
    //the first key of the sibling node after splitting
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{
    //Assuming that the sibling node is empty when the number of keys (the first 4 bytes) == 0
    int numKey = getKeyCount();
    //make sure the current node is full
    if(numKey < MAX_NLEAF_ENTRY){ 
        return RC_INVALID_FILE_FORMAT;
    }
    //find the location to insert the new key and pid
    int entryNum=0;
    int current_key;
    int entrySize=0;
    
    //Create buffer to hold sibling and this nodes data
    char* bothBuf = new char[PageFile::PAGE_SIZE+NLEAF_ENTRY_SIZE];
    memcpy(bothBuf, buffer, PageFile::PAGE_SIZE);
    
    while(entryNum<numKey){
        
        //page id comes before key
        memcpy(&current_key, buffer+sizeof(int)+entrySize+sizeof(PageId), sizeof(int));
        
        //if the new key is smaller than the current key, push back all the keys after this key
        //and insert the new (pid,key) entry
        //for example, if we have keyNum(3), pid(a), key(2), pid(b), key(3), pid(c), key(5), pid(d)
        //if we want to insert key(4), pid(f)
        //push back all the entry after entryNum=2: push back key(5),pid(d)
        //result: keyNum(4), pid(a), key(2), pid(b), key(3), pid(c),key(4), pid(f), key(5), pid(d)
        if(current_key>=key){
            int moveBufferSize = (numKey-entryNum) * NLEAF_ENTRY_SIZE;
            char* moveBuffer = (char*)malloc(moveBufferSize * sizeof(char));
            memcpy(moveBuffer, buffer+sizeof(int)+entrySize+sizeof(PageId), moveBufferSize);
            
            //add key first then pid
            memcpy(bothBuf+sizeof(int)+entrySize+sizeof(PageId), &key, sizeof(int));
            memcpy(bothBuf+sizeof(int)+entrySize+NLEAF_ENTRY_SIZE, &pid, sizeof(PageId));
            
            //add the buffer back in
            memcpy(bothBuf+sizeof(int)+entrySize+NLEAF_ENTRY_SIZE+sizeof(PageId), moveBuffer, moveBufferSize);
            
            //release memory
            free(moveBuffer);
            
            //increment key count
            numKey++;
            memcpy(buffer, &numKey, sizeof(int));
            break;
        }
        entryNum++;
        entrySize+=NLEAF_ENTRY_SIZE;
    }
    
    if(entryNum == numKey){
        //if the program reaches this point, the new Key is greater than all the keys in the node
        //add the new entry to the end
        //Note: we add key first, the pid
        memcpy(bothBuf+sizeof(int)+entrySize+sizeof(PageId),&key, sizeof(int));
        memcpy(bothBuf+sizeof(int)+entrySize+sizeof(PageId)+sizeof(int), &pid, sizeof(PageId));
    
        //increment key count
        numKey++;
        memcpy(buffer,&numKey,sizeof(int));
    }
    //There would not be the case when the insert key for non-leaf node is smaller than all the existing 
    //keys in the node because the insert key is being pushed from leaf (or child non-leaf), which is
    //the first key of the sibling node after splitting
    
    //This buffer created, 

    //Give sibling node its part of data
    char* sibStart = bothBuf + (sizeof(int) + (numKey-(numKey/2)+1)*NLEAF_ENTRY_SIZE);//Right after midkey
    int sibSize = (numKey-(numKey/2)-1)*NLEAF_ENTRY_SIZE + sizeof(PageId); //correctly rounds if odd or even keys
    char* sibBuf = new char[PageFile::PAGE_SIZE];
    memcpy(sibBuf+sizeof(int),sibStart, sibSize);//copy data into dummy buffer
    int sibKeys = numKey-(numKey/2)-1;//give dummy buffer correct # keys
    memcpy(sibBuf,&sibKeys,sizeof(int));
    sibling.read(sibBuf);//pass dummy data to silbing
    delete sibBuf;
    
    //Get this node's part of data
    memcpy(buffer, 0, PageFile::PAGE_SIZE);//clear current data
    memcpy(buffer, bothBuf, (sizeof(int) + (numKey/2)*NLEAF_ENTRY_SIZE + sizeof(PageId)));
    numKey= numKey/2;
    memcpy(buffer,&numKey,sizeof(int));
    delete bothBuf;
    
    return 0;
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{ 
     //Note: the entryNum for first key is 0 
    int numKey = getKeyCount();
    int entryNum=0;
    int key;

    //traverse through the node
    while(entryNum<numKey){
        //page id comes before key
        memcpy(&key, buffer+sizeof(int)+entryNum*NLEAF_ENTRY_SIZE+sizeof(PageId), sizeof(int));
        
        if(key>=searchKey){
            //retrive the PageId on the left of the key
            //for example, if we have keyNum(3), pid(a), key(2), pid(b), key(3), pid(c), key(5), pid(d)
            //and the search key is 4
            //we want to retrieve pid(c)
            //if search key is 6
            //we want pid(d)
            memcpy(&pid, buffer+sizeof(int)+entryNum*NLEAF_ENTRY_SIZE, sizeof(PageId));
            return 0;
        }
        entryNum++;
    }
    //if the program reaches this point, the search Key is greater than all the keys in the node
    //retrieve the right most pid
    memcpy(&pid, buffer+sizeof(int)+entryNum*NLEAF_ENTRY_SIZE, sizeof(PageId));
    return 0; 
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{ 
    if(pid1<0 || pid2<0)
        return RC_INVALID_PID;
    int numKey=1;
    memcpy(buffer,&numKey, sizeof(int));
    //copy (pid1,key,pid2)
    memcpy(buffer+sizeof(int), &pid1, sizeof(PageId));
    memcpy(buffer+sizeof(int)+sizeof(PageId), &key, sizeof(int));
    memcpy(buffer+2*sizeof(int)+sizeof(PageId), &pid2, sizeof(PageId));
    return 0; 

}